Computers provide branch operations or instructions to control the flow of execution of a computer program. These branch operations can either be unconditional or conditional branches. An unconditional branch (e.g., a "goto" statement) indicates that the flow of control is to transfer to the location designated by the branch, rather than to the next location after the branch. A conditional branch (e.g., an "if" statement) indicates that the flow of control is to transfer to the location designated by the branch only if the condition specified in the branch is satisfied. If the condition is not satisfied, then the flow of control continues at the location after the branch. Some computers provide branch operations in which the transfer location for the branch ("target") is stored in a specified target register. For example, a computer may provide several target registers that can be specified by a branch operation as containing the address of the target. Prior to executing a branch, the target register specified by that branch needs to be loaded with the address of the target of the branch. This loading of the target register is referred to as "defining the target register."
A compiler may generate code that uses the branch operations to affect function invocation. When the compiler encounters a function invocation, the compiler generates code to load a "call" target register with the address of the function, code to load a "return" target register with the return address to which the function is to return, and code to branch to the address indicated in the call target register. The compiler uses the same target register every time as the return target register. In this way, functions that are separately compiled can be invoked and know where the return address is stored. In addition, compilers may generate code, assuming that certain target registers are to be preserved by the calls to functions. If a called function uses such a target register, then the called function needs to save the value of target register when invoked and restore the saved value of the target register before returning from the call. These target registers are referred to as "callee save registers." Each function could have its own set of registers as callee save registers. However, in general, a compiler may by convention assume that the set of callee save registers is the same for all functions.
A compiler may also use branch operations to implement "switch statements" and "indirect calls" of a programming language. When generating code for a switch statement, the compiler generates code to calculate at runtime the target within the switch statement. Once that target is calculated, the address of the target can then be loaded into the target register that is specified in the branch operation. When generating code for an indirect call, the compiler may generate code to load the target register with a variable that contains the address of the function to be called.
Computer programs can have very complex flow of control. Their flow of control is often represented by a control flow graph ("CFG") that indicates the paths of execution between the "basic blocks" of the computer program. A "basic block" is generally considered to be a series of one or more instructions having one and only one entrance instruction (i.e., where control enters the block), and one and only one exit instruction (i.e., where control exits the block). A "control flow graph" is a well-known structure for representing the flow of execution between basic blocks of a program. A control flow graph is a directed graph in which each node of the graph represents a basic block. A control flow graph has a directed edge from a block B1 to a block B2 if block B2 can immediately follow block B1 in some path of execution. In other words, a control flow graph has a directed edge from block B1 to block B2 (1) if the last instruction of block B1 includes a conditional or unconditional branch to the first instruction of block B2, or (2) if block B2 immediately follows block B1 in the order of the program and block B1 does not end in an instruction that includes an unconditional branch.
Because computer programs have complex flows of control, the selection of which target registers to assign to which branch operations can have a significant impact on the efficiency of such programs. For example, if the compiler generates code that specifies the same target register for each branch operation, then the compiler needs to generate code to re-load that target register before each branch operation. Such re-loading can seriously impact the efficiency of the program. It would be desirable to have a system that would allocate target registers to a computer program in a way that tended to improve the overall efficiency of the computer program.